package com.lihepeng.leecode.array2;

/**
 * 二维数组的前缀和
 * 二维区域和检索 - 矩阵不可变
 *
 */
public class NumMatrix {
    int [][]preMartix;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        preMartix = new int[m+1][n+1];
        for (int i=0;i<=m;i++) {
            for (int j=0;j<=n;j++) {
                preMartix[i][j] = preMartix[i-1][j] +preMartix[i][j-1]+matrix[i-1][j-1] -preMartix[i-1][j-1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preMartix[row2+1][col2+1] -preMartix[row1][col2+1]-preMartix[row2+1][col1] + preMartix[row1][col1];
    }
}
